package com.zh.note.huawei.twohundred.组装新的数组;

import java.util.Arrays;

/**
 * @Author: zhanghuan
 * @date: 2023/8/11 10:55
 * @description: create it
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // String input = sc.nextLine();
        String input = "2 3";
        int[] nums = Arrays.stream(input.split(" ")).mapToInt(Integer::parseInt).toArray();
        // int sum = sc.nextInt();
        int sum = 5;
        if (nums.length == 0) {
            System.out.println(0);
            return;
        }
        int[][] dp = new int[nums.length][sum + 1];
        Arrays.stream(dp).forEach(row -> Arrays.fill(row, -1));
        Arrays.sort(nums);
        int minNum = nums[0];
        int res = dfs(nums, 0, 0, dp, sum, minNum);
        System.out.println(res);
    }

    // 深度优先搜索，index表示从数组的第几个元素开始搜索，sum表示当前已经选取的元素的和，min表示数组中最小的元素
    // targetSum表示要组成的和，
    private static int dfs(int[] nums, int index, int sum, int[][] dp, int targetSum, int minNum) {

        if (index >= nums.length) {
            return 0;
        }
        if (sum > targetSum) {
            return 0;
        }
        if (sum <= targetSum && targetSum - minNum < sum) {
            return 1;
        }
        if (dp[index][sum] != -1) {
            return dp[index][sum];
        }
        int count = 0; //count表示组装办法的数量

        for (int i = index; i < nums.length; i++) {
            count += dfs(nums, i, sum + nums[i], dp, targetSum, minNum);
        }
        dp[index][sum] = count;
        return dp[index][sum];
    }
}
